package sword.chapter5HashMap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 最小时间差
 * 将时间转为分钟制，列表排序，分别比较两两之间差值，找到最小差值
 * <p>
 * 细节
 * 需要比较最大时间和最小时间差，列表后再加一元素min + 24*60
 *
 * @author K
 * @date 2021/12/3 13:58
 */
public class S35FindMinDifference {
    /**
     * 网上题解
     * 更容易理解
     */
    public static int findMinDifferenceB(List<String> timePoints) {
        if (timePoints.size() > 24 * 60) {
            return 0;
        }
        List<Integer> mins = new ArrayList<>();
        for (String t : timePoints) {
            String[] time = t.split(":");
            mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]));
        }
        Collections.sort(mins);
        mins.add(mins.get(0) + 24 * 60);
        int res = 24 * 60;
        for (int i = 1; i < mins.size(); ++i) {
            res = Math.min(res, mins.get(i) - mins.get(i - 1));
        }
        return res;
    }

    /**
     * 个人编写
     * 解决不了最大和最小值之间的比较计算
     */
    public static int findMinDifference(List<String> timePoints) {
        int num = 60 * 24;
        if (timePoints.size() > num) {
            return 0;
        }
        boolean[] times = new boolean[num];
        for (String timePoint : timePoints) {
            String[] split = timePoint.split(":");
            int index = Integer.parseInt(split[0]) * 60 + Integer.parseInt(split[1]);
            if (times[index]) {
                return 0;
            }
            times[index] = true;
        }

        if (times[0] && times[num - 1]) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        int i = 0;
        while (i < num - 1) {
            if (times[i]) {
                int fast = i + 1;
                while (fast < num && !times[fast]) {
                    fast++;
                }
                if (fast == num) {
                    break;
                }
                if (times[fast]) {
                    min = Math.min(min, fast - i);
                }
                i = fast;
            } else {
                i++;
            }
        }
        return min;
    }

    /**
     * 书上题解
     */
    public static int findMinDifferenceA(List<String> timePoints) {
        if (timePoints.size() > 1440) {
            return 0;
        }

        boolean minuteFlags[] = new boolean[1440];
        for (String time : timePoints) {
            String t[] = time.split(":");
            int minute = Integer.parseInt(t[0]) * 60 + Integer.parseInt(t[1]);
            if (minuteFlags[minute]) {
                return 0;
            }

            minuteFlags[minute] = true;
        }

        return findMinDifference(minuteFlags);
    }

    private static int findMinDifference(boolean minuteFlags[]) {
        int minDiff = minuteFlags.length - 1;
        int prev = -1;
        int first = minuteFlags.length - 1;
        int last = -1;
        for (int i = 0; i < minuteFlags.length; ++i) {
            if (minuteFlags[i]) {
                if (prev >= 0) {
                    minDiff = Math.min(i - prev, minDiff);
                }

                prev = i;
                first = Math.min(i, first);
                last = Math.max(i, last);
            }
        }

        minDiff = Math.min(first + minuteFlags.length - last, minDiff);
        return minDiff;
    }

    public static void main(String[] args) {
//        List<String> timePoints = Arrays.asList("23:50", "23:59", "00:01", "23:58", "00:01");
        List<String> timePoints = Arrays.asList("12:12", "00:13");
//        int result = findMinDifference(timePoints);
        int resultA = findMinDifferenceA(timePoints);
//        int resultB = findMinDifferenceB(timePoints);
        System.out.println();
    }
}
